package com.gqb.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;


public class BinaryTreeBaseOnLinkHasThreePointer {
	
	private class Node{
		private String data;
		private Node leftNode;
		private Node rightNode;
		private Node parent;
		public Node(String data,Node parentNode) {
			super();
			this.data = data;
			this.parent=this.parent;
		}
		public String getData() {
			return data;
		}
		public void setData(String data) {
			this.data = data;
		}
		
		public Node getLeftNode() {
			return leftNode;
		}
		public void setLeftNode(Node leftNode) {
			this.leftNode = leftNode;
		}
		public Node getRightNode() {
			return rightNode;
		}
		public void setRightNode(Node rightNode) {
			this.rightNode = rightNode;
		}
		public Node getParent() {
			return parent;
		}
		public void setParent(Node parent) {
			this.parent = parent;
		}
	}
	private Node root;
	private int nodeCount;
	public BinaryTreeBaseOnLinkHasThreePointer(String data) {
		root=new Node(data, null);
	}
	
	private boolean addLeft(String parent,String data){
		Node parentNode=getNode(root, parent);
		parentNode.leftNode=new Node(data, parentNode);
		return true;
	}
	public boolean addRight(String parent,String data){
		Node parentNode=getNode(root, parent);
		parentNode.rightNode=new Node(data, parentNode);
		return true;
	}
	
	public int deep(Node root,int deep){
		int temp=0,tempL=0,tempr=0;
		if(root.leftNode!=null){
			tempL=deep(root.leftNode,deep+1);
			if(tempL>temp)
				temp=tempL;
		}
		if(root.rightNode!=null){
			tempr=deep(root.rightNode,deep+1);
			if(tempr>temp)
				temp=tempr;
		}
		
		return deep>temp?deep:temp;
		
	}
	public int getDepth(Node node,int depth){
		int tempL=0,tempR=0,temp=0;
		if(node.leftNode!=null){
			tempL=getDepth(node.leftNode, depth+1);
			if(tempL>temp){
				temp=tempL;
			}
		}
		if(node.rightNode!=null){
			tempR=getDepth(node.rightNode, depth+1);
			if(tempR>temp)
				temp=tempR;
		}
		return depth>temp?depth:temp;
	}
	/**
	 * 先序遍历查找点
	 * @param rootNode
	 * @param data
	 * @return
	 */
	private Node getNode(Node rootNode,String data){
		if(rootNode==null){
			System.out.println("树还未初始化");
			return null;
		}
		if(rootNode.getData().equals(data))
			return rootNode;
		Node node=null;
		if(rootNode.leftNode!=null){
			if(rootNode.leftNode.getData().equals(data))
			{
				node=rootNode.leftNode;
			}else {
				node=getNode(rootNode.leftNode, data);
			}
		}
		if(node==null&&rootNode.rightNode!=null){
			if(rootNode.rightNode.getData().equals(data))
			{
				return rootNode.getRightNode();
			}else{
				node=getNode(rootNode.getRightNode(), data);
			}
		}
		return node;
	}
	/**
	 * 广度优先遍历
	 * @return
	 */
	public List<Node> breadthFirst(){
		Queue<Node> treeQueue=new ArrayDeque<Node>();
		List<Node> list=new ArrayList<BinaryTreeBaseOnLinkHasThreePointer.Node>();
		treeQueue.add(root);
		while (!treeQueue.isEmpty()) {
			Node tempNode= treeQueue.poll();
			if(tempNode.leftNode!=null)
				treeQueue.add(tempNode.leftNode);
			if(tempNode.rightNode!=null)
				treeQueue.add(tempNode.rightNode);
			list.add(tempNode);
		}
		return list;
	}
	/**
	 * 先序遍历
	 * @param root
	 * @return
	 */
	public List<Node> firstIterator(Node root){
		List<Node> list=new ArrayList<>();
		list.add(root);
		if(root.leftNode!=null)
			list.addAll(firstIterator(root.leftNode));
		if(root.rightNode!=null){
			list.addAll(firstIterator(root.rightNode));
		}
		return list;
	}
	/**
	 * 中序遍历
	 * @param root
	 * @return
	 */
	public List<Node> middleIterator(Node root){
		if(root==null)
			return null;
		List<Node> list=new ArrayList<>();
		if(root.leftNode!=null)
			list.addAll(middleIterator(root.leftNode));
		list.add(root);
		if(root.rightNode!=null)
			list.addAll(middleIterator(root.rightNode));
		return list;
	}
	
	public static void main(String[] args) {
		BinaryTreeBaseOnLinkHasThreePointer tree=new BinaryTreeBaseOnLinkHasThreePointer("A");
		tree.addLeft("A", "B");
		tree.addRight("A", "C");
		tree.addLeft("B", "D");
		tree.addRight("B", "E");
		tree.addLeft("C", "F");
		tree.addLeft("D", "H");
		tree.addLeft("H", "R");
		System.out.println("树的深度为"+tree.deep(tree.root, 1));
		System.out.println("树的深度为"+tree.getDepth(tree.root, 1));
		List<Node> list=tree.breadthFirst();
		System.out.println("广度优先遍历");
		for (Node node : list) {
			System.out.print(node.data);
		}
		System.out.println("线序遍历");
		list=tree.firstIterator(tree.root);
		for (Node node : list) {
			System.out.print(node.data);
		}
		System.out.println("中序遍历");
		list=tree.middleIterator(tree.root);
		for (Node node : list) {
			System.out.print(node.data);
		}
	}
}
